import java.util.ArrayList;
import java.util.LinkedList;
/**
 * Created by L.jp
 * Description:给出一组数字，返回该组数字的所有排列
 * 例如：
 * [1,2,3]的所有排列如下
 * [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
 * （以数字在数组中的位置靠前为优先级，按字典序排列输出。）
 * User: 86189
 * Date: 2022-08-16
 * Time: 23:50
 */
public class Solution {
    //结果集
    static ArrayList<ArrayList<Integer>> ret=new ArrayList<>();
    public static ArrayList<ArrayList<Integer>> permute(int[] num) {
        
        //临时存储表
        LinkedList<Integer> tmp=new LinkedList<>();
        // 递归进行
        backTrack(num,tmp);
        return ret;
    }
    //递归+回溯
    private static void backTrack(int[] num, LinkedList<Integer> tmp) {
        //如果临时结果集的长度等于原数组长度，说明是一种排列
        if(tmp.size()== num.length){
            ret.add(new ArrayList<>(tmp));
            return;
        }
        //加入和撤销
        for (int j : num) {
            if (tmp.contains(j)) {
                continue;
            }
            //加入
            tmp.add(j);
            //递归加入下一个数
            backTrack(num, tmp);
            //撤销最后一个
            tmp.removeLast();
        }
    }
    
    public static void main(String[] args) {
        int[] num={1,2,3};
        System.out.println(permute(num));
    }
}
